#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<unordered_map>
using namespace std;

//1046.最后一块石头的重量
int lastStoneWeight(vector<int>& stones){
    //默认是大根堆，这里不写也可以
    priority_queue<int, vector<int>, greater> heap;
    for(auto num : stones){
        heap.push(num);
    }

    while(heap.size()>1){
        int y = heap.top();
        heap.pop();
        int x = heap.top();
        heap.pop();

        if(x!=y){
            heap.push(y - x);
        }
        else{
            continue;
        }
    }

    return heap.size() ? heap.top() : 0;
}

//703.数据流中的第K大元素
class KthLargest {
    //将小根堆设置位成员变量
    priority_queue<int, vector<int>, greater<int>> heap;
    //将小根堆的存储容量设置成K,存放的后K-1个就是数组中前k-1大的元素，堆顶就是第k大元素
    int _k;

public:
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for(auto num : nums){
            heap.push(num);
            //保证小根堆中只有k个
            if(heap.size()>_k){
                heap.pop();
            }
        }
    }
    
    int add(int val) {
        heap.push(val);
        if(heap.size()>_k){
            heap.pop();
        }
        return heap.top();
    }
};

//692.前k个高频单词
typedef pair<string, int> PSI;
struct cmp{
    bool operator()(const PSI cur1,const PSI cur2){
        //如果频次相同，按照字母的顺序建立大根堆
        if(cur1.second==cur2.second){
            return cur1.first < cur2.first;
        }
        //如果频次不相同，按照频次的个数建立小根堆
        return cur1.second > cur2.second;
    }
};
vector<string> topKFrequent(vector<string>& words, int k){
    //1.先将单词存放到哈希表中,建立字符串和频次的映射关系
    unordered_map<string, int> hash;
    for(auto s : words){
        hash[s]++;
    }

    //2.建立一个优先级队列
    priority_queue<PSI, vector<PSI>, cmp> heap;

    //3.遍历哈希表，将字符串和对应的频次存放到堆中
    for(auto& psi : hash){
        heap.push(psi);
        //如果堆中的个数大于k个，删除堆顶元素
        if(heap.size()>k){
            heap.pop();
        }
    }

    //4.将堆中的k个存放到结果数组中
    vector<string> ret(k);
    for (int i = k - 1; i >= 0; i++){
        ret[i] = heap.top().first;
        heap.pop();
    }

    return ret;
}

//295.数据流的中位数
class MedianFinder {
    //数据流的左半部分存放到大根堆中，堆顶元素就是左半部分的最右侧
    priority_queue<int> left;
    //数据流的右半部分存放到小根堆中，堆顶元素就是右半部分的最左侧
    priority_queue<int, vector<int>, greater<int>> right;

public:
    MedianFinder() {}
    
    void addNum(int num) {
        //左右要么个数相等，要么左边比右边多一个

        //如果大根堆的元素个数等于小根堆的元素个数
        if(left.size()==right.size()){
            //如果大根堆为空或者当前值小于等于大根堆堆顶元素，直接存放到大根堆中
            if(left.empty()||num<=left.top()){
                left.push(num);
            }
            //如果当前值大于大根堆堆顶元素，先存放到小根堆中，再将堆顶元素存放到大根堆中
            else{
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }

        //如果大根堆的元素个数不等于小根堆的元素个数
        else{
            //如果当前值小于等于大根堆堆顶元素，先存放到大根堆中，再将堆顶元素存放到小根堆中
            if(num<=left.top()){
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            //如果当前值大于大根堆堆顶元素，直接存放到小根堆中
            else{
                right.push(num);
            }
        }
    }
    
    double findMedian() {
        //如果左右个数相等，说明是偶数，返回两个堆的堆顶元素相加除以2.0
        //如果不相等，说明是奇数，返回左边的堆顶元素
        return left.size() == right.size() ? (left.top() + right.top()) / 2.0 : left.top();
    }
};

int main(){

    return 0;
}